package algorithms;

import java.util.Stack;

/**
 * 示例：
 * 输入字符串：<tag></tag> 这种形式就输出yes，否则就输出no.
 */
public class 字符串的标签对匹配 {
    public static void main(String[] args) {
        String str = "<a></a>";
        boolean b = matchPattern(str);
        System.out.println(b);
    }

    private static boolean matchPattern(String str) {
        Stack<String> lStack = new Stack<>();
        for (int i = 0; i < str.length(); ) {
            String nextTag = getNextTag(str, i);
            if (nextTag.startsWith("</")) {
                String pop = lStack.pop();
                if (!pop.substring(1).equals(nextTag.substring(2))) {
                    return false;
                }
            } else if (nextTag.startsWith("<")) {
                lStack.push(nextTag);
            } else {
                return false;
            }
            i = i + nextTag.length();
        }

        return lStack.isEmpty();
    }


    private static String getNextTag(String str, int start) {
        int state = 0;
        for (int i = start; i < str.length(); i++) {
            int scan = scan(str, i);
            switch (state) {
                case 0:
                    if (scan == '<') {
                        state = 1;
                    } else {
                        state = -1;
                    }
                    break;
                case 1:
                    if (scan == '/') {
                        state = 2;
                    } else if (isChar(scan)) {
                        state = 3;
                    } else {
                        state = -1;
                    }
                    break;
                case 2:
                    if (isChar(scan)) {
                        state = 3;
                    } else {
                        state = -1;
                    }
                    break;
                case 3:
                    if (scan == '>') {
                        return str.substring(start, i + 1);
                    } else if (isChar(scan)) {
                        state = 3;
                    } else {
                        state = -1;
                    }
                    break;
                case -1:
                    return "";

            }
        }
        return "";
    }

    private static final int EOF = -1;

    private static boolean isChar(int scan) {
        return !(scan == '<' || scan == '/' || scan == '>' || scan == EOF);
    }

    private static int scan(String s, int index) {
        if (index < s.length()) {
            return s.charAt(index);
        } else {
            return -1;
        }
    }

}
